//计数排序 -> 时间O(nlog(n)) , 空间O(count)
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArray(int* nums, int numsSize, int* returnSize) {
    int min = nums[0], max = nums[0];
    *returnSize = numsSize;
    for(int i = 0; i < numsSize; i++){
        if(min > nums[i])
            min = nums[i];
        if(max < nums[i])
            max = nums[i];
    }
    int count = max - min + 1;
    int *hash = (int*)malloc(sizeof(int) * count);
    memset(hash, 0, sizeof(int) * count);
    for(int i = 0; i < numsSize; i++){
        hash[nums[i] - min]++;
    }
    int j = 0;
    for(int i = 0; i < count; i++){
        while(hash[i]--){
            nums[j++] = i + min;
        }
    }
    free(hash);
    return nums;
}

//归并排序 -> 时间O(nlog(n)) , 空间O(n)
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void _MergeSort(int* a, int left, int right, int* tmp) {
	if (left >= right)
		return;

	int mid = (left + right) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//类似合并两个有序链表
	int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] <= a[begin2]) {
			tmp[index++] = a[begin1++];
		}
		else {
			tmp[index++] = a[begin2++];
		}
	}

	//拷贝剩余数据
	while (begin1 <= end1) {
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[index++] = a[begin2++];
	}

	//拷贝回原数组
	for (int i = left; i <= right; i++) {
		a[i] = tmp[i];
	}
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
	_MergeSort(nums, 0, numsSize - 1, tmp);
	free(tmp);
    return nums;
}

/*给你一个整数数组 nums，请你将该数组升序排列。

你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。*/